// 无重复字符的最长子串
// 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
  // 滑动窗口初始化为一个空数组
  let arr = [];
  // 要返回的字符串的长度
  let max = 0;
  for (let i = 0; i < s.length; i++) {
    // 使用 indexOf 判断是否在数组中出现过
    let index = arr.indexOf(s[i])
    // 如果出现过
    if (index !== -1) {
      // 从数组开头到当前字符串全部截取掉
      arr.splice(0, index + 1);
    }
    // 在窗口右边放进新的字符
    arr.push(s.charAt(i));//charAt(i)返回指定位置的字符
    // 更新下最大值
    max = Math.max(arr.length, max);//两个数比较
  }
  // 返回
  return max;
};


// 二叉树先序遍历
function preorder(root) {
    // 递归边界，root 为空
    if(!root) {
        return 
    }
     
    // 输出当前遍历的结点值
    console.log('当前遍历的结点值是：', root.val)  
    // 递归遍历左子树 
    preorder(root.left)  
    // 递归遍历右子树  
    preorder(root.right)
}
// 二叉树中序遍历
function inorder(root) {
    // 递归边界，root 为空
    if(!root) {
        return 
    }
     
    // 递归遍历左子树 
    inorder(root.left)  
    // 输出当前遍历的结点值
    console.log('当前遍历的结点值是：', root.val)  
    // 递归遍历右子树  
    inorder(root.right)
}
// 二叉树的后序遍历
function postorder(root) {
    // 递归边界，root 为空
    if(!root) {
        return 
    }
     
    // 递归遍历左子树 
    postorder(root.left)  
    // 递归遍历右子树  
    postorder(root.right)
    // 输出当前遍历的结点值
    console.log('当前遍历的结点值是：', root.val)  
}


// 1. Map 的妙用----两数求和问题
const nums = [2, 7, 11, 15], target = 9
const twoSum = function (nums, target) {
  const diffs = {}
  const len = nums.length
  for (let i = 0; i < len; i++) {
    if (diffs[target - nums[i]] !== undefined) {
      return [diffs[target - nums[i]], i]
    }
    diffs[nums[i]] = i
  }
}

// 2. 强大的双指针法----合并两个有序数组
const nums1 = [1, 2, 3, 0, 0, 0], m = 3
const nums2 = [2, 5, 6], n = 3
const merge = function(nums1, m, nums2, n) {
  let i = m - 1, j = n - 1, k = m + n - 1
  while(i >= 0 && j >= 0) {
    if (nums1[i] >= nums2[j]) {
      nums1[k] = nums1[i]
      i--
      k--
    } else {
      nums1[k] = nums2[j]
      j--
      k--
    }
  }

  while(j>=0) {
    nums1[k] = nums2[j]
    k--
    j--
  }
}
// 3. 对撞指针----三数求和问题
const nums3 = [-1, 0, 1, 2, -1, -4]
const threeSum = function(nums) {
  let res = []
  nums = nums.sort((a, b) => {
    return a - b
  })
  const len = nums.length
  for (let i = 0; i < len - 2; i++) {
    let j = i + 1
    let k = len - 1
    if (i > 0 && nums[i] === nums[i - 1]) {
      continue
    }
    while(j  < k) {
      if (nums[i] + nums[j] + nums[k] < 0) {
        j++
        while(j < k && nums[j] === nums[j - 1]) {
          j++
        }
      } else if (nums[i] + nums[j] + nums[k] > 0) {
        k--
        while(j < k && nums[k] === nums[k + 1]) {
          k--
        }
      } else {
        res.push([nums[i], nums[j], nums[k]])
        j++
        k--
        while(j < k && nums[j] === nums[j - 1]) {
          j++
        }
        while(j < k && nums[k] === nums[k + 1]) {
          k--
        }
      }
    }
  }
  return res
}

// 4. 翻转字符串
const str = 'juejin'
const res = str.split('').reverse().join('')
console.log(res)

// 5. 判断一个字符串是否是回文字符串
// 方法1 翻转字符串
function isPalindrome(str) {
  const reversedStr = str.split('').reverse().join('')
  return reversedStr === str
}

// 方法2 结合对称性来做判断
function isPalindrome(str) {
  const len = str.length
  for(let i = 0; i < len/2; i++) {
    if (str[i] !== str[len - 1 - i]) {
      return false
    }
  }
  return true
}

// 6.回文字符串的衍生问题， 给定一个非空字符串s, 最多删除一个字符。判断是否能成为回文字符串
const validPalindrome = function(s) {
  const len = s.length
  
  let i = 0, j = len - 1

  while(i < j && s[i] === s[j]) {
    i++ 
    j--
  }
  
  if (isPalindrome(i + 1, j)) {
    return true
  }

  if (isPalindrome(i, j - 1)) {
    return true
  }

  function isPalindrome(st, ed) {
    while(st < ed) {
      if (s[st] !== s[ed]) {
        return false
      }
      st++
      ed--
    }
    return true
  }

  return false
}

// 7. 字符串匹配问题----正则表达式初相见
/**
 * 构造函数
 */
const WordDictionary = function () {
  // 初始化一个对象字面量，承担 Map 的角色
  this.words = {}
};

/**
  添加字符串的方法
 */
WordDictionary.prototype.addWord = function (word) {
  // 若该字符串对应长度的数组已经存在，则只做添加
  if (this.words[word.length]) {
    this.words[word.length].push(word)
  } else {
    // 若该字符串对应长度的数组还不存在，则先创建
    this.words[word.length] = [word]
  }

};

/**
  搜索方法
 */
WordDictionary.prototype.search = function (word) {
  if (!this.words[word.length]) {
    return false
  }
  const len = word.length
  if (!word.includes('.')) {
    return this.words[len].includes(word)

  }

  const reg = new RegExp(word)

  return this.words[len].some((item) => {
    return reg.test(item)
  })
};

// 8.正则表达式更进一步----字符串与数字之间的转换问题
const myAtoi = function(str) {
    const reg = /\s*([-\+]?[0-9]*).*/
    const groups = str.match(reg)
    const max = Math.pow(2,31) - 1
    const min = -max - 1
    let targetNum = 0
    if(groups) {
        targetNum = +groups[1]
        if(isNaN(targetNum)) {
            targetNum = 0
        }
    }
    if(targetNum > max) {
        return max
    } else if( targetNum < min) {
        return min
    }
    return targetNum
};
// 9. 链表 
// 创建链表结点，需要使用构造函数
function ListNode(val) {
  this.val = val 
  this.next = null
}
// 10. 链表的合并
// 真题描述：将两个有序链表合并为一个新的有序链表并返回。
// 新链表是通过拼接给定的两个链表的所有结点组成的。 
// 示例： 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
let l1 = {
  val: 1,
  next: {
    val: 2, 
    next: {
      val: 4,
      next: null
    }
  }
}
let l2 = {
  val: 1, 
  next: {
    val: 3,
    next: {
      val: 4,
      next: null
    }
  }
}
const mergeTwoLists = function(l1, l2) {
  let head = new ListNode()
  let cur = head
  while(l1 && l2) {
    if (l1.val <= l2.val) {
      cur.next = l1 
      l1 = l1.next
    } else {
      cur.next = l2 
      l2 = l2.next
    }
    cur = cur.next
  }

  cur.next = l1 !== null ? l1 : l2

  return head.next
}

// 11. 链表结点的删除
// 真题描述：给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
// 示例 1:
// 输入: 1->1->2
// 输出: 1->2
// 示例 2:
// 输入: 1->1->2->3->3
// 输出: 1->2->3
const deleteDuplicates = function(head) {
  let cur = head
  while(cur !=null && cur.next !=null) {
    if (cur.val === cur.next.val) {
      cur.next = cur.next.next
    } else {
      cur = cur.next
    }
  }
  return head
}

// 12. 删除问题的延伸----dummy结点登场
// 真题描述：给定一个排序链表，删除所有含有重复数字的结点，
// 只保留原始链表中 没有重复出现的数字。
// 示例 1:
// 输入: 1->2->3->3->4->4->5
// 输出: 1->2->5
// 示例 2:
// 输入: 1->1->1->2->3
// 输出: 2->3
const deleteDuplicates2 = function(head) {
  if (!head || !head.next) {
    return head
  }
  let dummy = new ListNode() 
  dummy.next = head 
  let cur = dummy 
  while(cur.next && cur.next.next) {
    if (cur.next.val === cur.next.next.val) {
      let val = cur.next.val 
      while(cur.next && cur.next.val === val) {
        cur.next = cur.next.next
      }
    } else {
      cur = cur.next
    }
  }

  return dummy.next
}

// 13.快慢指针----删除链表的倒数第N个结点
// 真题描述：给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
// 示例： 给定一个链表: 1->2->3->4->5, 和 n = 2.
// 当删除了倒数第二个结点后，链表变为 1->2->3->5.
// 说明： 给定的 n 保证是有效的。
const removeNthFromEnd = function(head, n) {
  const dummy = new ListNode()
  dummy.next = head
  let fast = dummy
  let slow = dummy

  while(n!==0) {
    fast = fast.next 
    n--
  }

  while(fast.next) {
    fast = fast.next
    slow = slow.next
  }
  
  slow.next = slow.next.next 

  return dummy.next
}

// 14. 多指针法----链表的反转
// 真题描述：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。
// 示例:
// 输入: 1->2->3->4->5->NULL
// 输出: 5->4->3->2->1->NULL
const reverseList = function(head) {
  let pre = null 
  let cur = head 
  while(cur !== null) {
    let next = cur.next 
    cur.next = pre 
    pre = cur 
    cur = next 
  }

  return pre
}

// 15. 局部反转一个链表
// 真题描述：反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
// 说明: 1 ≤ m ≤ n ≤ 链表长度。
// 示例:
// 输入: 1->2->3->4->5->NULL, m = 2, n = 4
// 输出: 1->4->3->2->5->NULL
const reverseBetween = function(head, m, n) {
  let pre, cur, leftHead 
  const dummy = new ListNode() 
  dummy.next = head 
  let p = dummy 
  for (let i = 0; i < m - 1; i++) {
    p = p.next
  }
  leftHead = p 
  let start = leftHead.next 
  pre = start 
  cur = pre.next 
  for (let i = m; i < n; i++) {
    let next = cur.next 
    cur.next = pre 
    pre = cur 
    cur = next
  }

  leftHead.next = pre 
  start.next = cur 
  return dummy.next
}

// 16. 环形链表基本问题——如何判断链表是否成环？
// 真题描述：给定一个链表，判断链表中是否有环。
// 示例 1：
// 输入：[3,2,0,4]（链表结构如下图） 输出：true
// 解释：链表中存在一个环
const hasCycle = function(head) {
  while(head) {
    if (head.flag) {
      return true
    } else {
      head.flag = true 
      head = head.next
    }
  }
  return false
}

// 快慢指针法
function hasCycle(head) { 
  if (!head || !head.next)  {
    return false
  }
    
  let slow = head 
  let fast = head
  while(fast && fast.next) {
    slow = slow.next 
    fast = fast.next.next 
    if (slow === fast) {
      return true
    }
  }
  return false
}

// 哈希表
function hasCycle(head) {
  if (!head) {
    return false
  }
  const visited = new Set()

  while(head) {
    if (visited.has(head)) {
      return true
    }
    visited.add(head)
    head = head.next
  }
  return false
}

// 17. 环形链表衍生问题——定位环的起点
// 真题描述：给定一个链表，返回链表开始入环的第一个结点。 如果链表无环，则返回 null。
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const detectCycle = function(head) {
  while(head){
    if(head.flag){
      return head;
    }else{
      head.flag = true
      head = head.next
    }
  }
  return null
}

function hasCycle(head) { 
  if (!head || !head.next)  {
    return null
  }
    
  let slow = head 
  let fast = head
  while(fast && fast.next) {
    slow = slow.next 
    fast = fast.next.next 
    if (slow === fast) {
      return fast
    }
  }
  return null
}







// 18. 典型真题快速上手-“有效括号”问题
// 题目描述：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
// 有效字符串需满足： 左括号必须用相同类型的右括号闭合。
// 左括号必须以正确的顺序闭合。
// 注意空字符串可被认为是有效字符串。
// 示例 1:
// 输入: "()"
// 输出: true

// 示例 2:
// 输入: "()[]{}"
// 输出: true

// 示例 3:
// 输入: "(]"
// 输出: false

// 示例 4:
// 输入: "([)]"
// 输出: false

// 示例 5:
// 输入: "{[]}"
// 输出: true

// 用一个 map 来维护左括号和右括号的对应关系
const leftToRight = {
  "(": ")",
  "[": "]",
  "{": "}"
}
const isValid = function(s) {
  if (!s) {
    return true
  }
  const stack = []
  const len = s.length 
  for (let i = 0; i < len; i++) {
    const ch = s[i]
    if (ch === "(" || ch === "{" || ch === "[") {
      stack.push(leftToRight[ch])
    } else {
      if (!stack.length || stack.pop() !== ch) {
        return false
      }
    }
  }

  return !stack.length
}

// 19.栈问题进阶-每日温度问题
// 题目描述: 根据每日气温列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。
// 如果之后都不会升高，请在该位置用 0 来代替。

// 例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

// 提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
/**
 * @param {number[]} T
 * @return {number[]}
 */
// 入参是温度数组
const dailyTemperatures = function(T) {
    const len = T.length // 缓存数组的长度 
    const stack = [] // 初始化一个栈   
    const res = (new Array(len)).fill(0) //  初始化结果数组，注意数组定长，占位为0
    for(let i=0;i<len;i++) {
      // 若栈不为0，且存在打破递减趋势的温度值
      while(stack.length && T[i] > T[stack[stack.length-1]]) {
        // 将栈顶温度值对应的索引出栈
        const top = stack.pop()  
        // 计算 当前栈顶温度值与第一个高于它的温度值 的索引差值
        res[top] = i - top 
      }
      // 注意栈里存的不是温度值，而是索引值，这是为了后面方便计算
      stack.push(i)
    }
    // 返回结果数组
    return res 
};

// 20. 栈的设计——“最小栈”问题
// 题目描述：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
// push(x) —— 将元素 x 推入栈中。
// pop() —— 删除栈顶的元素。
// top() —— 获取栈顶元素。
// getMin() —— 检索栈中的最小元素s
/**
 * 初始化你的栈结构
 */
const MinStack = function() {
  this.stack = []
};

/** 
 * @param {number} x
 * @return {void}
 */
// 栈的入栈操作，其实就是数组的 push 方法
MinStack.prototype.push = function(x) {
  this.stack.push(x)
};

/**
 * @return {void}
 */
// 栈的入栈操作，其实就是数组的 pop 方法
MinStack.prototype.pop = function() {
  this.stack.pop()
};

/**
 * @return {number}
 */
// 取栈顶元素，咱们教过的哈，这里我本能地给它一个边界条件判断（其实不给也能通过，但是多做不错哈）
MinStack.prototype.top = function() {
  if(!this.stack || !this.stack.length) {
      return 
  }
  return this.stack[this.stack.length - 1]
};

/**
 * @return {number}
 */
// 按照一次遍历的思路取最小值
MinStack.prototype.getMin = function() {
    let minValue = Infinity  
    const  { stack } = this
    for(let i=0; i<stack.length;i++) {
        if(stack[i] < minValue) {
            minValue = stack[i]
        }
    }
    return minValue
};



const MinStack = function() {
    this.stack = [];
    // 定义辅助栈
    this.stack2 = [];
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.stack.push(x);
    // 若入栈的值小于当前最小值，则推入辅助栈栈顶
    if(this.stack2.length == 0 || this.stack2[this.stack2.length-1] >= x){
        this.stack2.push(x);
    }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    // 若出栈的值和当前最小值相等，那么辅助栈也要对栈顶元素进行出栈，确保最小值的有效性
    if(this.stack.pop() == this.stack2[this.stack2.length-1]){
        this.stack2.pop();
    }
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return this.stack[this.stack.length-1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    // 辅助栈的栈顶，存的就是目标中的最小值
    return this.stack2[this.stack2.length-1];
};



// 21.如何用栈实现一个队列？
// 题目描述：使用栈实现队列的下列操作：
// push(x) -- 将一个元素放入队列的尾部。
// pop() -- 从队列首部移除元素。
// peek() -- 返回队列首部的元素。
// empty() -- 返回队列是否为空。

// 示例: MyQueue queue = new MyQueue();
// queue.push(1);
// queue.push(2);
// queue.peek(); // 返回 1
// queue.pop(); // 返回 1
// queue.empty(); // 返回 false
/**
 * 初始化构造函数
 */
const MyQueue = function () {
  // 初始化两个栈
  this.stack1 = [];
  this.stack2 = [];
};

/**
* Push element x to the back of queue.
* @param {number} x
* @return {void}
*/
MyQueue.prototype.push = function (x) {
  // 直接调度数组的 push 方法
  this.stack1.push(x);
};

/**
* Removes the element from in front of queue and returns that element.
* @return {number}
*/
MyQueue.prototype.pop = function () {
  // 假如 stack2 为空，需要将 stack1 的元素转移进来
  if (this.stack2.length <= 0) {
    // 当 stack1 不为空时，出栈
    while (this.stack1.length !== 0) {
      // 将 stack1 出栈的元素推入 stack2
      this.stack2.push(this.stack1.pop());
    }
  }
  // 为了达到逆序的目的，我们只从 stack2 里出栈元素
  return this.stack2.pop();
};

/**
* Get the front element.
* @return {number}
* 这个方法和 pop 唯一的区别就是没有将定位到的值出栈
*/
MyQueue.prototype.peek = function () {
  if (this.stack2.length <= 0) {
    // 当 stack1 不为空时，出栈
    while (this.stack1.length != 0) {
      // 将 stack1 出栈的元素推入 stack2
      this.stack2.push(this.stack1.pop());
    }
  }
  // 缓存 stack2 的长度
  const stack2Len = this.stack2.length;
  return stack2Len && this.stack2[stack2Len - 1];
};

/**
* Returns whether the queue is empty.
* @return {boolean}
*/
MyQueue.prototype.empty = function () {
  // 若 stack1 和 stack2 均为空，那么队列空
  return !this.stack1.length && !this.stack2.length;
};

// 22.滑动窗口问题
// 题目描述：给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
// 示例: 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7]

// 编码实现1: 双指针+遍历法
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
const maxSlidingWindow = function (nums, k) {
  // 缓存数组的长度
  const len = nums.length;
  // 定义结果数组
  const res = [];
  // 初始化左指针
  let left = 0;
  // 初始化右指针
  let right = k - 1;
  // 当数组没有被遍历完时，执行循环体内的逻辑
  while (right < len) {
    // 计算当前窗口内的最大值
    const max = calMax(nums, left, right);
    // 将最大值推入结果数组
    res.push(max);
    // 左指针前进一步
    left++;
    // 右指针前进一步
    right++;
  }
  // 返回结果数组
  return res;
};

// 这个函数用来计算最大值
function calMax(arr, left, right) {
  // 处理数组为空的边界情况
  if (!arr || !arr.length) {
    return;
  }
  // 初始化 maxNum 的值为窗口内第一个元素
  let maxNum = arr[left];
  // 遍历窗口内所有元素，更新 maxNum 的值
  for (let i = left; i <= right; i++) {
    if (arr[i] > maxNum) {
      maxNum = arr[i];
    }
  }
  // 返回最大值
  return maxNum;
}

// 编码实现2：双端队列法